package top.coderkim.leetcode.graph;

import java.util.ArrayList;
import java.util.List;

public class LC133CloneGraph {

    static class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    static class Solution {
        int V=1000;
        boolean[] marked = new boolean[V];
        Node[] copied = new Node[V];

        public Node cloneGraph(Node node) {
            if (node==null) {  //空图
                return node;
            }
            Node source = new Node(node.val, new ArrayList<>(node.neighbors));
            dfs(source);
            return source;
        }

        void dfs(Node node) {
            marked[node.val] = true;
            copied[node.val] = node;
            if (node.neighbors==null || node.neighbors.isEmpty()) {
                return;
            }

            int num=node.neighbors.size();
            for (int idx=0; idx<num; idx++) {
                Node w=node.neighbors.get(idx);
                if (w==null) {
                    continue;
                }
                if (marked[w.val]) {
                    Node w1 = copied[w.val];
                    node.neighbors.set(idx, w1);
                    continue;
                }
                Node w2=new Node(w.val, new ArrayList<>(w.neighbors));
                dfs(w2);
                node.neighbors.set(idx, w2);
            }
        }

    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node newNode = (new Solution()).cloneGraph(node);
    }
}
